package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 基数排序(基于桶排序的方法)
 * 计数排序时空间换时间的经典算法，在运算大量的数据时，会消耗大量的内存，会出现OOM(OutOfMemertError)
 * 此基数排序不支持负数的运算
 *
 * @author WangJX
 * @version 1.0
 * @date 2019/11/7 10:24
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 543, 748, 14, 214, -118, 0, -21, -45, -100};

        //创建一个80000的随机数组
//        int[] arr = new int[80000000];
//        for (int i = 0; i < 80000000; i++) {
//            arr[i] = (int) (Math.random() * 8000000);
//        }
//
//        //查看排序使用的时间
//        Date d1 = new Date();
//        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        System.out.println(sdf.format(d1));

//        radixSort(arr);
        radixSortAtMinus(arr);
//
//        Date d2 = new Date();
//        System.out.println(sdf.format(d2));


        System.out.println(Arrays.toString(arr));
    }

    /**
     * 基数排序(分桶排序)
     *
     * @param arr
     */
    public static void radixSort(int[] arr) {

        //找出数组中最大的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        //求出最大数的位数
        int count = (max + "").length();


        //定义10个桶存放数据
        int[][] bucket = new int[10][arr.length];

        //定义10个桶各自的索引
        int[] bucketCount = new int[bucket.length];

        for (int i = 0, j = 1; i < count; i++, j *= 10) {
            //对数组中的数据进行遍历，根据条件放入桶中
            for (int k = 0; k < arr.length; k++) {
                //取出数据的个位、十位、百位....
                int lastNum = arr[k] / j % 10;
                //放入对应规则的桶中 并记录每个桶中数据放入了多少个
                bucket[lastNum][bucketCount[lastNum]++] = arr[k];
            }

            //按照顺序取出10个桶中的数据到arr数组中
            int index = 0;
            for (int k = 0; k < bucketCount.length; k++) {
                if (bucketCount[k] != 0) {
                    for (int l = 0; l < bucketCount[k]; l++) {
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //取完数据后清空索引中的数据
                bucketCount[k] = 0;
            }
        }
    }


    /**
     * 使用基数排序解决处理负数问题
     * 使用绝对值
     *
     * @param arr
     */
    public static void radixSortAtMinus(int[] arr) {

        //找出数组中最大的位数
        int max = Math.abs(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if (max < Math.abs(arr[i])) {
                max = arr[i];
            }
        }

        //求出最大数的位数
        int count = (max + "").length();


        //定义10个桶存放数据
        int[][] bucket = new int[10][arr.length];

        //定义10个桶各自的索引
        int[] bucketCount = new int[bucket.length];
        //增加负数的索引
        int[] bucketCountMinus = new int[bucket.length];

        for (int i = 0, j = 1; i < count; i++, j *= 10) {
            //对数组中的数据进行遍历，根据条件放入桶中
            for (int k = 0; k < arr.length; k++) {
                if (arr[k] < 0) {
                    int lastNum = Math.abs(arr[k]) / j % 10;
                    bucket[lastNum][bucketCount[lastNum]++] = arr[k];
                    bucketCountMinus[lastNum]++;
                } else {
                    //取出数据的个位、十位、百位....
                    int lastNum = arr[k] / j % 10;
                    //放入对应规则的桶中 并记录每个桶中数据放入了多少个
                    bucket[lastNum][bucketCount[lastNum]++] = arr[k];
                }

            }

            //按照顺序取出10个桶中的数据到arr数组中
            int index = 0;
            //先从10到0中取负数的值先放入arr中
            for (int k = bucketCount.length - 1; k >= 0; k--) {
                if (bucketCountMinus[k] != 0) {
                    for (int l = 0; l < bucketCount[k]; l++) {
                        //循环遍历桶中的数据，判断是否是负数
                        if (bucket[k][l] < 0) {
                            //是负数则先放入arr中
                            arr[index] = bucket[k][l];
                            index++;
                        }
                    }
                }
                //取完负数的数据后清空索引中的数据
                bucketCountMinus[k] = 0;
            }
            //在从0到10取正数
            for (int k = 0; k < bucketCount.length; k++) {
                if (bucketCount[k] != 0) {
                    for (int l = 0; l < bucketCount[k]; l++) {
                        //循环判断桶中的数是否是正数
                        if (bucket[k][l] >= 0) {
                            arr[index] = bucket[k][l];
                            index++;
                        }
                    }
                }
                //取完数据后清空索引中的数据
                bucketCount[k] = 0;
            }
        }
    }
}
